package cn.guyouda.algorithms.sort;

/**
 * Shell排序
 *
 * @author Youda
 */
public class ShellSort {
    public static void shellSort(Comparable[] src) {

        int N = 3; //排序间隔

        int length = src.length; //数组长度
        int h = 1;

        while (h < length / N) {
            h = N * h + 1;
        }

        while (h >= 1) {
            for (int i = h; i < length; i++) {
                for (int j = i; j >= h && less(src[j], src[j - h]); j -= h) {
                    exchange(src, j, j - h);
                }
            }

            h = h / N;

        }

    }


    //比较x是否小于y
    public static boolean less(Comparable x, Comparable y) {
        return x.compareTo(y) < 0;
    }

    //交换 x,y
    public static void exchange(Comparable[] src, int x, int y) {
        Comparable z = src[x];
        src[x] = src[y];
        src[y] = z;
    }


    public static void main(String[] args) {

        //测试数据
        String[] src = {"a", "x", "z", "i", "y", "o", "l", "q", "b", "d", "z", "s", "c"};
        Integer[] src1 = {100, 99, 70, 98, 99, 101, 3, 6, 676, 45, 25, 77, 80, 1, 0, 46, 28, 11111, 56666, 22, 6, 8, 29};

        System.out.println("===========原数组==========");
        for (String str : src) {
            System.out.print(str + ",");
        }

        shellSort(src); //排序

        System.out.println();
        System.out.println("==========排序后==========");
        for (String str : src) {
            System.out.print(str + ",");
        }


        System.out.println();
        System.out.println("==========原数组=========");
        for (int i = 0; i < src1.length; i++) {
            System.out.print(src1[i] + ",");
        }

        shellSort(src1);

        System.out.println();
        System.out.println("==========排序后==========");
        for (int i = 0; i < src1.length; i++) {
            System.out.print(src1[i] + ",");
        }

    }


}
